/*
 * @lc app=leetcode.cn id=108 lang=golang
 *
 * [108] 将有序数组转换为二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	n := len(nums)

	if n == 3 {
		return &TreeNode{
			Val:   nums[1],
			Left:  &TreeNode{Val: nums[0]},
			Right: &TreeNode{Val: nums[2]},
		}
	}
	if n == 2 {
		return &TreeNode{
			Val:  nums[1],
			Left: &TreeNode{Val: nums[0]},
		}
	}
	if n == 1 {
		return &TreeNode{
			Val: nums[0],
		}
	}
	mid := n / 2
	root := &TreeNode{Val: nums[mid]}
	left := sortedArrayToBST(nums[:mid])
	right := sortedArrayToBST(nums[mid+1:])
	root.Left = left
	root.Right = right
	return root
}

// @lc code=end

